package com.jjlin.chapter_1;

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
class Pet{
    private String type;
    public Pet(String type){
        this.type = type;
    }
    public String getType(){
        return this.type;
    }
}
class Cat extends Pet{
    public Cat(String type){
        super(type);
    }
}

class Dog extends Pet{
    public Dog(String type){
        super(type);
    }
}

class PetEnter{
    private int count;//猫狗的入队时间
    private Pet pet;
    private int id;//猫狗的编号
    public PetEnter(Pet pet, int count, int id){
        this.count = count;
        this.pet = pet;
        this.id = id;
    }

    public Pet getPet(){
        return this.pet;
    }

    public int getCount(){
        return this.count;
    }

    public int getId(){
        return this.id;
    }

    public String getPetType(){
        return this.pet.getType();
    }
}

class CatDogQueue{
    private Queue<PetEnter> catQueue;
    private Queue<PetEnter> dogQueue;
    private int count;

    public CatDogQueue(){
        catQueue = new LinkedList<PetEnter>();
        dogQueue = new LinkedList<PetEnter>();
        count = 0;
    }

    public void add(Pet pet, int id){
        if(pet.getType().equals("dog")){
            this.dogQueue.add(new PetEnter(pet, count++, id));
        }else if(pet.getType().equals("cat")){
            this.catQueue.add(new PetEnter(pet,count++, id));
        }else
            throw new RuntimeException("error, not cat or dog!");
    }

    public ArrayList<PetEnter> pollAll(){
        ArrayList<PetEnter> res = new ArrayList<>();
        while(!catQueue.isEmpty() && !dogQueue.isEmpty()){
            if(catQueue.peek().getCount() < dogQueue.peek().getCount())
                res.add(catQueue.poll());
            else
                res.add(dogQueue.poll());
        }
        while(!catQueue.isEmpty())
            res.add(catQueue.poll());
        while(!dogQueue.isEmpty())
            res.add(dogQueue.poll());
        return res;
    }

    public ArrayList<PetEnter> pollDog(){
        if(dogQueue.isEmpty())
            throw new RuntimeException("error, dog queue is empty!");
        ArrayList<PetEnter> res = new ArrayList<>();
        while(!dogQueue.isEmpty())
            res.add(dogQueue.poll());
        return res;
    }

    public ArrayList<PetEnter> pollCat(){
        if(catQueue.isEmpty())
            throw new RuntimeException("error, cat queue is empty!");
        ArrayList<PetEnter> res = new ArrayList<>();
        while(!catQueue.isEmpty())
            res.add(catQueue.poll());
        return res;
    }

    public boolean isEmpty(){
        if(catQueue.isEmpty() && dogQueue.isEmpty())
            return true;
        return false;
    }

    public boolean isDogEmpty(){
        return dogQueue.isEmpty();
    }

    public boolean isCatEmpty(){
        return catQueue.isEmpty();
    }

}

public class CD100{
    public static void CD100(String[] args){
        CatDogQueue queue = new CatDogQueue();
        Scanner sc = new Scanner(System.in);
        int cut = sc.nextInt();
        sc.nextLine();
        for(int i = 0; i < cut; i++){
            String s = sc.nextLine();
            String str[] = s.split(" ");
            if("add".equals(str[0])){
                int num = Integer.parseInt(str[2]);
                if("cat".equals(str[1]))
                    queue.add(new Pet("cat"), num);
                else
                    queue.add(new Pet("dog"), num);
            }else if("pollAll".equals(str[0])){
                ArrayList<PetEnter> list = queue.pollAll();
                for(int j = 0; j < list.size(); j++)
                    System.out.println(list.get(j).getPet().getType() + " " + list.get(j).getId());
            }else if("pollCat".equals(str[0])){
                ArrayList<PetEnter> list = queue.pollCat();
                for(int j = 0; j < list.size(); j++)
                    System.out.println(list.get(j).getPet().getType() + " " + list.get(j).getId());
            }else if("pollDog".equals(str[0])){
                ArrayList<PetEnter> list = queue.pollDog();
                for(int j = 0; j < list.size(); j++)
                    System.out.println(list.get(j).getPet().getType() + " " + list.get(j).getId());
            }else if("isEmpty".equals(str[0])){
                System.out.println(queue.isEmpty() ? "yes" : "no");
            }else if("isDogEmpty".equals(str[0])){
                System.out.println(queue.isDogEmpty() ? "yes" : "no");
            }else if("isCatEmpty".equals(str[0])){
                System.out.println(queue.isCatEmpty() ? "yes" : "no");
            }
        }
    }
}